package offer.diff;

import java.util.Arrays;

/**
 * @author DengYuan2
 * @create 2021-03-16 19:06
 */
public class n_10_4 {
    public static void main(String[] args) {
        n_10_4 n = new n_10_4();
        int res = n.jumpFloorII(5);
        System.out.println(res);
    }

    public int jumpFloorII(int target) {
//        if (target<=2){
//            return target;
//        }
//        int[] count = new int[target];
//        count[0]=1;
//        count[1]=2;
//        for (int i = 2; i < target; i++) {
//            for (int j = 0; j < i; j++) {
//                count[i]+=count[j];
//            }
//            count[i]++;
//        }

        //如下改进
        int[] count = new int[target];
        Arrays.fill(count,1);
        for (int i = 1; i < target; i++) {
            for (int j = 0; j < i; j++) {
                count[i]+=count[j];
            }
        }
        return count[target-1];
    }

    public int jumpFloorII2(int target) {
        if (target<0){
            return -1;
        }
        if (target==1){
            return 1;
        }
        return 2*jumpFloorII2(target-1);
    }

    public int jumpFloorII3(int target) {

        return (int)Math.pow(2,target-1);
        //如下，用位移操作，更快
//        return 1<<(target-1);
    }
}
